package learn;

import org.jetbrains.annotations.NotNull;

import java.util.ArrayList;
import java.util.List;

public class Kmp {

    public static void main(String[] args) {
        String s = "ababaababcb";
        String t = "ababc";
        Integer[] ans = Kmp.getIndexs(s, t);
        for (int q : ans) {
            System.out.print(q + ", ");
        }
    }

    private static int[] next;

    /**
     * 根据模板串生成next数组。
     * next[i]存储的是模板串[0,i-1]的最长可匹配前缀后缀的长度，
     * (关键点) 等价于可匹配前缀的末尾的下一个位置。
     * 所以在之后的匹配中若发现模板串i处为坏字符，那么就可以逻辑上
     * 移动模板串，使得最长可匹配前缀的下一个字符与坏字符相对应
     */
    private static void generateNext(@NotNull String template) {
        next = new int[template.length() + 1];
        int dump = 0;
        for (int i = 1; i < template.length(); ++i) {
            if (template.charAt(dump) == template.charAt(i))
                dump += 1;
            else
                dump = 0;
            next[i + 1] = dump;
        }
    }

    public static Integer[] getIndexs(@NotNull String src, String tmp) {
        List<Integer> es = new ArrayList<Integer>();
        generateNext(tmp);
        int dump = 0;
        for (int i = 0; i < src.length(); ++i) {
            while (dump > 0 && tmp.charAt(dump) != src.charAt(i))
                dump = next[dump];
            if (tmp.charAt(dump) == src.charAt(i)) {
                dump += 1;
                if (dump == tmp.length()) { // 完美匹配
                    es.add(i - tmp.length() + 1);   // 保存主串中匹配的位置
                    dump = next[dump];
                }
            }
        }
        return es.toArray(new Integer[0]);
    }
}
